#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr)
            return head;
        ListNode *p = head, *q = p->next;
        q = p->next == nullptr ?: p->next;
        while (q != nullptr)
        {
            p->next = q->next;
            q->next = head;
            head = q;
            q = p->next;
        }
        return head;
    }

    // 递归法
    ListNode *reverse(ListNode *pre, ListNode *cur)
    {
        if (cur == NULL)
            return pre;
        ListNode *temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
    
    ListNode *reverseListRecursion(ListNode *head)
    {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

private:
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
};

int main()
{
    // TODO
    return 0;
}
